Round Overview
Discuss this match
In a warm up match between two important TCO rounds, coders were ready to show their worth. The problem set turned to be worthy training. In division 1, less than 30 coders solved more than one problem and nobody was able to correctly solve the hard problem. Among the small elite that solved two problems, speed and challenges defined who would get the first place. RAD. managed to score an SRM win by combining the second fastest submission for the 500-points problem and a succesful challenge. Following very closely: theycallhimtom, ardiankp, anrieff (with almost 400 points in challenges) and sycoacquired the remaining places in the top 5.
In division 2, 10 coders were able to correctly solve all three problems. Of them, grep and KiraZ dominated and got the first and second place, respectively.
TheAlmostLuckyNumbersDivTwo
Problem Details
Used as: Division Two - Level One:
Value | 250 |
Submission Rate | 750 / 867 (86.51%) |
Success Rate | 687 / 750 (91.60%) |
High Score | hemant_gangolia for 249.95 points (0 mins 24 secs) |
Average Score | 211.34 (for 687 correct submissions) |
As usual, let us begin by checking the constraints. There are at most 1000000 numbers in the range from a to b. 1000000 is not a high number. So we could first try all values x in the range and for each, verify if it is almost lucky and then count it in that case. Given a fixed number x, it is simple to verify if it is an almost lucky number. Extracting digits of a number is a classical task and it should also be possible to use your language’s features to convert the number to a string and then iterating through its digits and counting those that are not 4 or 7. If the total is more than 1, the number is not almost lucky. Since we can tell whether a number x is almost lucky, we can repeat that procedure with each number in the range and count those that are almost lucky.
The maximum number of digits of a number between 1 and 1000000 is 7. Though for most of those numbers, we have only 6 digits (those from 100000 to 999999). 1000000 total numbers from a to b multiplied by 6 gives us 6000000 as an upper bound for the number of operations that we will need. Since that is actually a fairly low amount, we can be sure that this simple approach should run in time in TC’s server. The following Java code takes around 0.25 seconds in its worst case:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int find(int a, int b) {
int count = 0;
// For each x:
for (int x = a; x <= b; x++) {
//Verify if x is almost lucky.
String s = "" + x;
//By counting the number of unlucky digits
int unlucky = 0;
for (int i = 0; i < s.length(); i++) {
char d = s.charAt(i);
if ((d != '7') && (d != '4')) {
unlucky++;
}
}
// If the number is lucky, increment the count
if (unlucky <= 1) {
count++;
}
}
return count;
}
TheLuckyGameDivTwo
Problem Details
Used as: Division Two - Level Two:
Value | 500 |
Submission Rate | 449 / 867 (51.79%) |
Success Rate | 150 / 449 (33.41%) |
High Score | wiliamchen for 491.93 points (3 mins 39 secs) |
Average Score | 286.83 (for 150 correct submissions) |
There are two decision problems that we can consider each separately: Given a range picked by John, Brus has to pick a range of bLen numbers that contains the least amount of lucky numbers. The second one is: Given the range a-b, John must pick a range of jLen numbers such that Brus’ pick contains as many lucky numbers as possible. Let us begin with John’s decision.
Let us assume that we know how to solve Brus’ subproblem and let us skip to solving John’s. Assuming that we are in the worst case possible : a = 1, b = 4747. Then there are at most 4747 options for the starting point of John’s interval. Assuming Brus’ solution does not take much time, we could assume that we can simply call it once per each possible choice of John and then pick the maximum result for John.
When solving Brus’ subproblem, there are also at most 4747 choices for the beginning of the range he will pick. After we have a given range of Brus’ choice we need to count the number of lucky numbers in that range. If we were to also try all possible of Brus’ choices, there would be 4747 of them. The product 4747*4747 is actually large, so we should have a quick way to, given a potential Brus’ choice, count the total number of lucky numbers in that range.
Quickly counting the number of lucky numbers in a range
This is not as hard as it sounds. The trick is that we can precalculate some information before running the cycles that are needed for John’s and Brus’ decisions. For example, we could first add all the lucky numbers to a list. Since we do not care about numbers greater than 4747, we only need the lucky numbers with 4 or less digits. There are 24 + 23 + 22 + 2 of them. (For each digit position, there are two choices (4 or 7), so for each number of digits, there are 2npossible lucky numbers.) So we can save all those lucky numbers (at most 32) to a list. In total, the decision problem would need at most 4747*4747*32 operations, or more formally: O(b * b * 2log_10(b)) operations (Which is actually O(b * b * b1/3.32)). It is actually low enough. But it is not hard to optimize it to O(b * b). Since the maximum number of a range is 4747, simply use an array lowerLucky[x] that returns the total number of lucky numbers less than a number x. This array is useful when calculating the number of lucky numbers between two integers p and q, inclusive: that is lowerLucky[q+1] - lowerLucky[p]. In order to precalculate this array, simply iterate through each value of x. If x is lucky, then (lowerLucky[x+1] = lowerLucky[x] + 1) else (lowerLucky[x+1] = lowerLucky[x]). To check if a number is lucky, go through its digits like in the previous problem.
Summary
* Both John’s and Brus’ decisions have a small range of choices, so we can brute force each of them. It requires a nested O(b*b) loop to work.
* It needs a quick way to calculate the number of lucky numbers inside a range. This is simple to do by prior precalculation of a list of lucky numbers, or of an array that contains the count of lucky numbers below each number.
Code
The following Java code takes less than 0.1 seconds in its worst case:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
boolean isLucky(int x) {
String s = "" + x;
for (char ch: s.toCharArray()) {
if (ch != '4' && ch != '7') {
return false;
}
}
return true;
}
public int find(int a, int b, int jLen, int bLen) {
//Generate the lowerLucky array
int[] lowerLucky = new int[b + 2];
lowerLucky[0] = 0;
for (int x = 1; x <= b; x++) {
lowerLucky[x + 1] = lowerLucky[x] + (isLucky(x) ? 1 : 0);
}
int mxJohn = 0;
//Try every possible start for John's interval,
//Pick the one which ends with the most lucky numbers
for (int jStart = a; jStart + jLen - 1 <= b; jStart++) {
int mnBrus = 1000000;
//Try every possible start for Brus' interval
//pick the one with the least lucky numbers
for (int bStart = jStart; bStart + bLen - 1 <= jStart + jLen - 1; bStart++) {
int c = lowerLucky[bStart + bLen] - lowerLucky[bStart];
mnBrus = Math.min(mnBrus, c);
}
mxJohn = Math.max(mxJohn, mnBrus);
}
return mxJohn;
}
TheLuckyBasesDivTwo
Problem Details
Used as: Division Two - Level Three:
Value | 1000 |
Submission Rate | 107 / 867 (12.34%) |
Success Rate | 14 / 107 (13.08%) |
High Score | grep for 766.27 points (16 mins 48 secs) |
Average Score | 524.44 (for 14 correct submissions) |
Let us first consider the most straightforward approach: brute force for all bases possible and count the ones in which the number is lucky. In order to use that approach we would need two things: a) An upper bound for the bases to check. And b) A quick way to know if a given base is lucky or not. Regarding b), the idea to use this approach should actually come from the observation that it is actually simple and relatively fast to verify if the number is lucky in a given base x. In order to extract the base x digits out of n when the base is fixed, the procedure is the same as when the base is our own base 10, but using the new base. To elaborate, the number n is equal to a certain polynomial:
n = D0 * x0 + D1 * x1 + D2 * x2 + …
(Note that x0 = 1.) This comes directly from the numeric base definition that is present even in the problem statement. The first digit D0 is actually equal to (n % x) (where % is the modulooperator, which returns the remainder of the integer division n/x). It is because you can tell that D0 is smaller than x (by definition) and that the other terms in the polynomial are all multiples of x. After extracting the first digit, we are interested in the next ones and we should remove the first digit out of n. The simplest way is to simply divide n by x (integer division). So we get:
D0 = n % x
n/x = D1 * x0 + D2 * x1 + …
What happens after dividing n by x is that the D0 part is discarded as the remainder and what is left is similar to the original case. In fact, if we denote the new value of n as n’, we can tell that D1 = (n’ % x) , and then n’’ = n’/x. We can repeat this process until n is equal to 0.
Therefore, we can extract digits easily (and the extraction works in O( Logx(n)) time, because we divide n by x until it becomes 0). We need the second requirement to use the simple loop approach: an upper bound for the base to check. For this, let us return to the extraction of the first digit: (D0 = n % x). If x was larger than n then D0 would be equal to n and the next n’ = n / x would be 0. This happens to every base that is greater than n. So, the numeric representation of n in that base would not change. This has two consequences:
* Certain numbers will be lucky in infinitely many bases. This is something that is mentioned by the statement, and is true: all bases larger than n give the same representation for n, one in which the first and only digit is equal to n. If n was 4 or 7, then all of the bases greater than n would be lucky, because the representation would always be 4 or 7. So, in case n is equal to 4 or 7, we should directly return -1.
* The maximum base we need to check is n. This happens because in the case n was not 4 or 7, then all the bases greater than n would not be lucky.
We now have an upper bound for the bases we have to check, it is n. There is a problem with this, however. If we need to check all bases from 2 to n, then we have an O(n) loop. Inside the loop, we need an O(log(n)) loop to extract the digits and count them. In total, the approach needs O(n*log(n)) time. n can be as large as 1012 and that is way too high to run in time.
The key observation to overcome this problem is that, as we increase the base x, the number of digits should decrease. For example, the number 512 needs 10 digits in base 2, but only 3 digits in base 10 and one digit in base 513. Cases with few digits are not complicated to handle. We already know which numbers cause n to have 1 digit. Let us describe a way to count all the bases that will make n a lucky number with 2 digits.
We want a base x such that the number n has two digits and is lucky. There are only 4 possible numbers that are lucky and have two digits: 44, 47, 74 and 77. Let us focus on counting the bases for which n is equal to 47. By the way that numeric systems work, we want to find an x that solves the following polynomial:
4 * x + 7 = n x = (n - 7) / 4
Since x is the only unknown variable, this equation has at most one solution, so there is only one base x in which n will be equal to 47. Note that there are many conditions. The base x must be a integer number. So (n - 7) must be a multiple of 4. The base must also be larger than both 7 and 4. (If x was smaller than 4, then number 4 could not be a valid digit.) This process can be generalized to each pair of digits (a, b):
a * x + b = n x = (n - b) / a
// (n - b) divides a, x > a , x > b
Given a pair (a,b) of digits (which can be (4,4), (4,7), (7,4) or (7,7)), if (n - b) is a multiple of a and the result (x = (n - b) / a) is greater than both a and b, then there exists a base x such that n is equal to (a b) when represented in that base. After trying each of these pairs and counting those that are possible, we can have the total count of lucky bases in which n has 2 digits.
Back to the simple loop approach. Since we already know the number of 2-digit bases, we do not need to count them. Thus we only need to count the bases that yield numbers that have more than 2 digits. Remember that as the base increases, the number of digits decreases, so we can calculate the maximum base that will yield a 3-digit number and all bases smaller than this base will yield more than 2 digits. If the base x has 3 digits, we have:
Max x: n = D2 * x2 + D1 * x1 + D0
We can assume that D2, D1 and D0 are all non-negative integers. If we want x to be as large as possible, then these numbers would have to be as small as possible, and that means that D1 and D0 would be 0. D2 has to be at least one though because else the number would actually not have three digits. Therefore we have:
n = x2.
Which means that x may be at most the square root of n. In other words, for a base to have three or more digits, the base should not exceed the square root of n. Thanks to this, we only need to check all bases that are <= sqrt(n) and count those that are lucky. This means that the simple bruteforce approach’s complexity has become O(sqrt(n) * log(n)). Note that this is only possible because we do 4 O(1) operations to count the bases that yield 2-digit numbers.
Summary
* If n is 4 or 7, all infinitely many bases greater than n are lucky. Return -1.
* Split the remaining cases in two parts. Count the number of lucky bases that make n have two digits and the number of lucky bases that make n have more than two digits separately.
* When a base has two digits, n will be 44, 47, 77 or 47. For each of these cases we can solve the equation a * x + b = n to find the base. This needs to be validated because the base must be integer and greater than a and b.
* In the remaining cases, we can use a bruteforce loop and try all possible bases from 2 to the square root of n. Convert n to each of those bases and count those that are lucky.
* Adding both results together yields the final answer.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
long count3DorMore(long n) {
// counts all the bases x such that the base
// is lucky and n in that base has at least 4 digits
//
// (b*b*b will always be <= n)
//
long cnt = 0;
for (long b = 2; b <= n; b++) {
int cdigits = 0;
long x = n;
boolean luck = true;
while (x > 0) {
luck = luck && (x % b == 4 || x % b == 7);
x /= b;
cdigits++;
}
if (cdigits <= 2) {
break;
}
if (luck) {
cnt++;
}
}
return cnt;
}
boolean canDoPair(long n, long a, long b) {
// Does a x exist such that:
// (x : a*x + b = n)
// x > a, x > b ?
long ax = n - b;
if (ax % a == 0) {
long x = ax / a;
return (x > a && x > b);
}
return false;
}
long count2D(long n) {
// counts all the bases x such that the base
// is lucky and n is a two digit number in that base
//
long r = 0;
for (long a = 4; a <= 7; a += 3) {
for (long b = 4; b <= 7; b += 3) {
r += (canDoPair(n, a, b) ? 1 : 0);
}
}
return r;
}
public long find(long n) {
if (n == 4 || n == 7) {
// Any base > n will be lucky.
return -1;
}
long res = 0;
res += count3DorMore(n);
res += count2D(n);
return res;
}
There is a binary search-based approach. Remember that there is a limited number of combinations of 4 and 7 that may be representations of n. We may consider picking each of these combinations and verifying if there is a base that represents n as that combination of digits. Let us estimate the maximum number of such combinations. For that we first need a maximum number of digits. As usual, the higher the base, the smaller the number of digits, and vice versa. Base 2 yields the largest amount of digits needed to represent n. However, note that no number can be lucky in base 2, because digits 4 and 7 do not belong to base 2. So, the base needs to be at least 5. The number of digits of n in base 5 is the base 5 logarithm of n. For n = 10^12, the result is 18 digits. However, base 5 does not allow digit 7 which means there is only one digit available. This means that there are at most 18 base-5 numbers that could be equal to n. The same is true for bases 6 and 7. Base 8 finally allows both lucky digits, the base 8 logarithm of 10^12 is : 13.28. Which means we need at most 14 digits when 4 and 7 are allowed.
The sum of all combinations of 4 and 7 with at most 14 digits is: 22 + 23 + … 214. Which is around 215. To those combinations, we need to add the remaining 4 numbers of 15, 16, 17 and 18 digits that contain only 4s (to handle bases 5, 6 and 7). The total amount is (215+4).
For each of those combinations, we need to verify if there exists a base x in which n becomes equal to that combination. Let us, for example try a 3 digits combination:
P(x) = D2 * x2 + D1 * x1 + D0 = n
Note that the solution is also going to be unique, because we need x to be positive and the solution should be unique for any combination. This equation is more complicated than the one for 2 digit numbers, but still it should be possible to solve it. We also need to solve more complicated equations for combinations of more digits. The easier to implement general approach to solving these equations is binary search, since we want the result x to be an integer. We can change the problem into maximizing the value of x:
max(x) : P(x) = D2 * x2 + D1 * x1 + D0 <= n
If we find the maximum x that follows that equation, then the polynomial P(x) for this maximum will either be equal to n (in that case, the maximum x is the solution to the equation) or it will be smaller than n, in which case, there is no integer solution for that equation. After changing the problem to a maximization one with a condition, let us call C(x) a boolean function that is true if ( P(x) <= n) and false otherwise. If C( x) is true, then for any value (y < x): C(y) will be true because the polynomial P(y) will always be smaller than P(x) and thus also smaller than n. If C(x) is false, then for any value (y> x): C(y) will also be false (because P(y) will be forcefully greater than P(x) which is greater than n). We can also easily tell that C(0) will be true, because ( P(0) = 0 ) and (0 <= n). Also, C(n+1) will be false. Therefore, we can do a binary search to find the maximum x such that C(x) is true.
If we can generate all the valid combinations and do a binary search for each one to validate it, we can count all the lucky bases for a given n. The complexity is around O(2log_8(n)+1 * log(n) ) which is actually O( n1/3* log(n) ) after some operations.
Another Solution.
n = D0 * x0 + D1 * x1 + D2 * x2 + …
Divide n into 2 parts:
n = (D0 * x0) + (D1 * x1 + D2 * x2 + …)
Let a= D0 * x0 ,
b = D1 * x1 + D2 * x2 + …
Then b = x * (D1 * x0 + D2 * x1 + D3 * x2 + …)
This means x|b, which means the lucky bases must divide b.
In order for x to be a lucky base then a can only be either 4 or 7. Then b can be either (n-4) or (n-7).
The potential lucky bases are the factors (primes and non primes) of these 2 numbers (n-4) and (n-7).
Get the factors then loop through all these factors and count the number of lucky bases.
TheAlmostLuckyNumbersDivOne
Problem Details
Used as: Division One - Level One:
Value | 250 |
Submission Rate | 380 / 576 (65.97%) |
Success Rate | 254 / 380 (66.84%) |
High Score | Petr for 247.29 points (2 mins 59 secs) |
Average Score | 164.62 (for 254 correct submissions) |
Unlike the easier version, this time it should not be possible to go through a to b and check if each of those numbers is an almost lucky number. There are going to be at most 10^16 numbers between a and b. It is still a counting problem in which the values we are counting follow some combined conditions. In problems like this one, a good step is to estimate just about how many of the elements being counted will there be at most. If the value turns out to be fairly small, then we can use a bruteforce / backtracking approach to count them. Do not let the 64-bit return type confuse you, in reality the total number of almost lucky numbers between 1 and 10^16 is not very high. Let us try to estimate this number. Numbers that are smaller than or equal to 10^16 will have at most 16 digits. 10^16 (1 with 16 zeros) can be ignored because it contains more than one unlucky digit. Let us first try the numbers that are completely lucky (contain only 4 or 7): (216 + … + 23 + 22 + 2). This is because for each fixed number of digits L there are 2L ways to place a 4 or a 7 in each position. The sum is equal to (217-2 = 131070). The number of almost lucky numbers that contain one unlucky digit is different. For a number of digits L, pick a location L in which to place a digit different than 4 or 7 and place 4 or 7 to the other digit positions: this yields L * 2L-1 * 8. Lbecause of the choice of L positions, 2L-1 ways to place 4s or 7s in the remaining positions and 8 because of the choice of 8 digits different than 4 or 7 for the unlucky position. In total we have: (168215 + … + 281 + 8), the sum is 7864328. The total there are 131070 + 7864328 = 7995398 numbers.
That value is low, however, it may have been very complicated to go through all that effort during the match. It is possible to make easier estimates that are also useful. For example, you could have said that out of 217 choices for completely lucky numbers we multiply the number of them by 128 (16 * 8) (because for each of these choices we can add a new unlucky digit at one of at most 16 positions). The result for that rough estimation is 16777216, which we know is larger than the real value, but is still low enough for the next step.
Backtracking
We know that the maximum number of almost lucky numbers is actually not very big and around 8 digits-long. In counting problems where the elements being counted are composed of parts and the total of elements is not actually very high, we can consider Backtracking as an alternative. This approach may be called DFS (because it is basically a Depth-first search in a implicit graph) or brute force (because we do try all values as well). But we will call it backtracking because we will make sure to crop partial solutions that we are sure won’t take us to a valid one. The main idea in backtracking is to use recursion to generate a list/vector of components that make a solution. In our case, the parts are digits and the solution is an almost lucky number. We begin with an empty number, this number is 0. Then the backtracking function will take a number x as an argument -- the current number representing our list of digits.
* We will make sure to never add more than 1 unlucky digit. Then x will be almost lucky. However, we also need to verify that it is between a and b, inclusive. In that case, we can increase the total.
* If x is greater than b, then we should stop adding more digits as any number with more digits will also be greater than b.
* For each instance, we can add a digit to x, this will create a new number with that digit appended, and we should recurse using this new number. Since we should never add more than two unlucky digits, we should have add an argument uAdded to the function to remember if a unlucky digit has already been added so to avoid doing it twice. This argument is true if we have already added an unlucky digit.
* A special case is digit 0. We should only add that digit to numbers that are not empty. Else we will end in an infinite loop.
In each of the called instances of the function, x will be an almost lucky number. So the backtracking function will not be called more than 7995398 times. In each of these calls we may need at most 10 operations (one for each digit that we try to add). In total we will not use less than 7995398*10 steps, which is enough to run in time in Topcoder’s servers.
Summary
The maximum of almost lucky numbers that we need to count is at most 7995398. This is low enough for us to do a backtracking solution that just generates each number as a list of digits that only contains at most one unlucky digit.
Code
The following is a Java implementation of the backtracking idea. It needs 0.3 seconds in its worst case.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class TheAlmostLuckyNumbersDivOne {
long a, b, total;
void backtrack(long x, boolean uAdded) {
if (x <= b) {
if (x >= a) {
// x is an almost lucky number
//between a and b, inclusive.
total++;
}
if (!uAdded) {
//We can add unlucky digits:
for (int d = 1; d < 10; d++) {
if (d != 4 && d != 7) {
//Recurse with the added digit
// (mark uAdded as true):
backtrack(x * 10 + d, true);
}
}
// We can add 0 once we have already
// added a non-zero digit:
if (x != 0) {
backtrack(x * 10, true);
}
}
// add 4 or 7 as digit:
backtrack(x * 10 + 4, uAdded);
backtrack(x * 10 + 7, uAdded);
}
}
public long find(long a, long b) {
this.a = a;
this.b = b;
total = 0;
backtrack(0, false);
return total;
}
}
TheLuckyGameDivOne
Problem Details
Used as: Division One - Level Two:
Value | 500 |
Submission Rate | 113 / 576 (19.62%) |
Success Rate | 32 / 113 (28.32%) |
High Score | theycallhimtom for 354.65 points (19 mins 59 secs) |
Average Score | 230.93 (for 32 correct submissions) |
This problem is similar to TheLuckyGameDivTwo, but with much higher constraints. Let us consider this explanation to be a continuation of the one of the easier version. Thus it may be a good idea to first try solving that easier version before reading this explanation.
Like in the easier version of the problem, TheLuckyGameDivTwo, we must consider two decision problems. The large constraints are surely going to make things more complicated. Note, however, that there are (210+29+…22) = 2046 lucky numbers smaller than 10^10. This small value is most likely going to be useful. There are three sub-problems. In this situation we will begin talking about Brus’s problem.
Brus’s problem
Let us assume that John has already picked a range of numbers between start and end, inclusive. Brus must pick a bLen sized interval of numbers such that it contains the minimum amount of lucky numbers. In this situation, it will pay to formalize things a bit: let us call F(x) the total number of lucky numbers that exist between x and x + bLen - 1, inclusive. (That is, the number of lucky numbers that would be in Brus’ picked interval if it starts at x.) This time, there are many possible choices for x. It may be any of the numbers between start and end - bLen + 1, inclusive. There are jLen numbers between start and end and bLen may be 1, so the maximum number of positions that Brus may try is equal to the maximum value of jLen. In this case, that is 10^10, very large for any approach based on trying each of them. The function F(x) is also going to be complicated to implement, but for now let us assume we know how to handle it and focus only on Brus.
We have a range (start, end - bLen + 1 ) of numbers of which we need to pick a x such that F(x) is minimum. All of the numbers will be part of an interval. So, we need to calculate: min(F(start), F(start+1), …, F(i), F(i+1), … F(end - bLen + 1)). What should be noticeable here is that the interval that begins at i will have numbers in common with the interval that begins at (i+1). What is more important though, is the difference. We can then see that the move from the interval that begins at i to the interval that begins at (i+1) is equivalent to removing number i and adding (i+bLen) to replace it.
( i, i+1, … , i + bLen - 1) -> (i+1, i+2, … , i + bLen)
* Assume that i is a lucky number, then F(i+1) cannot be greater than F(i). In fact, the only way for F(i+1) to be equal to F(i) is if (i+bLen) is lucky else F(i+1) will be smaller than F(i). So we have F(i+1) <= F(i).
* If i is not a lucky number then F(i+1) cannot be smaller than F(i) because if number (i+bLen) is lucky then F( i+1) will be greater than F(i) and if (i+bLen) is not lucky then (F(i+1) = F(i)). So we have F(i+1) >= F(i).
From the second conclusion we have that for every non-lucky number i: F(i+1) >= F(i). Since we are interested only in finding the minimum F(x) we should not consider F(i+1). This also translates to every sequence of non-lucky numbers. Imagine a sequence of unlucky numbers k, k+1, …, k+T. Since none of these numbers is lucky then we can claim that: F(k+T) >= F(k+T-1) >= …) >= F(k+1) >= F(k) , so we would only need to consider F(k).
From the first conclusion: if i is lucky, then F(i+1) will always be <= F(i). Note that for every lucky number i, (i+1) will not be lucky. This means that we should never need to get F(i) for a lucky number because F(i+1) will be at least as small. Note also that since (i+1) is unlucky, then F(i1) will also be <= F(i+2). In fact, F(i+1) should be less than or equal to all the F(j) for each unlucky number j that follows i. As an overall conclusion, the only numbers that matter to us when minimizing F(x) are all numbers (i+1) such that i is a lucky number. So when given a range [start, end-bLen+1] , we should calculate F(i+1) for each (i+1) that belongs to that range such that i is lucky. The minimum over those values will be the minimum possible F(x) for all the values in the range. There is, however a small catch. Although F( start) may be <= F(start-1) if (start-1) is not lucky, we cannot consider F(start-1) as it does not belong to the allowed range, so F(start) may also be a possible minimum. Make sure to consider F(start) when minimizing the result for Brus. In total, we need to consider F(a) and also F(i+1) for every (i+1) in range such that i is lucky thus will need a O(L) loop for Brus’ decision, where L is the number of lucky numbers between a and b (at most 2046).
John’s turn
Let us continue with the formalization. We have a range [a, b] from which we have to pick a start of John’s interval of length jLen that will be used by Brus to pick a minimum from and we want the number of lucky numbers in the minimum interval picked by Brus to be the maximum possible. The allowed values for start are actually all those that belong to the range [a, b - jLen + 1]. Let us call the function that returns Brus’ result B(x). Note that:
B( x) = min( F(x), F(x+1), … F(x + jLen - bLen) ).
( x + jLen - bLen comes from (x + jLen - 1 - bLen + 1).) As with moving from F(i) to F(i+1) there is a conversion between B( x) and B(x+1):
min( F(x), F(x+1), … F(x + jLen - bLen) ) -> min( F(x+1), F(x+2), … F(x + jLen - bLen + 1) ) .
It also works backwards, the move from B(x+1) to B(x) involves removing the number at the tail and adding F(x) to the minimum function:
min( F(x+1), F(x+2), … F(x + jLen - bLen + 1) ) -> min( F(x), F(x+1), … F(x + jLen - bLen) ) .
There is the possibility that F(x + jLen - bLen + 1) was the only value equal to B(x+1), which means that all the other values F( x+1), F(x+2),… were greater than F(x + jLen - bLenn + 1). If this happens then the minimum between (x+1) and (x + jLen - bLen), inclusive, has increased. We also need to add the new element F(x). Note then that if F(x) >= F(x+1) we can be certain that (B(x) >= B(x + 1)).
From that conclusion, if we knew that (F(i-1) >= F(i)), then we can know that (B(i-1) >= B(i)). We are interested in finding the maximum value of B(x). So, we can ignore all i such that: (F(i-1) >= F(i)). In other words to calculate max(B(a), B(a+1), B(a+2), … ) we should only consider the values of i such that ( F(i-1) < F(i) ). Which are those values? Note that there can be a transition from F(i) to F(i-1):
( i, i + 1, … i + bLen - 1) -> (i-1, i, …, i + bLen -2)
The element that is being removed is (i + bLen - 1). This element is lucky if and only if F(i-1) <= F(i). Because there is a possibility that the newly added element, (i-1) is lucky which would make the F(i) and F(i-1) equal. This observation is helpful because we can claim that (i + bLen - 1) being lucky is a necessary condition for (F(i-1) < F(i)). In other words, the numbers i such that (F(i-1) < F(i)) must be such that (i + bLen - 1) is lucky. If (j = i + bLen - 1) is lucky then i is equal to ( j - bLen + 1). So, for each lucky number j between a and b, inclusive, there is a chance that ( F(j - bLen + 1) < F(j - bLen) ). Which means that (i = j - bLen + 1) could be the best position from which to start John’s interval. Since we cannot skip from B(a) to B(a-1), we should also consider B(a). In total, there are O(L) candidate positions for John to start his interval.
The lucky numbers
Right now, we need two cycles totaling O(L*L) to pick John’s candidate positions and Brus’s candidate positions nested in them. L is at most 2046. Note that we have not thought of a way to calculate F(x) yet. Since it will be called O(L*L) times, it should be a fast function. Also note that John’s and Brus’s algorithms each assume that we have a list of all the lucky numbers between a and b. This list can be generated quickly with a backtracking solution similar to the one used in the division 1 250 problem (remember that there are at most 2046 of these numbers).
If we assume that we have generated that list, and the list is sorted, then it should be possible to answer the query [Number of elements between x and x+bLen-1, inclusive] using binary search. We can use binary search to implement a function countLower(x) that yields the total number of lucky numbers less than x. Then the total number of lucky numbers in a range [x, x+bLen-1], inclusive would be: (countLower(x+bLen) - countLower(x)).
Summary
* It can be shown that the only relevant locations at which John can begin his interval are: a and also (j - bLen + 1), for each lucky number j.
* Similarly, it can be shown that the only relevant locations at which Brus can begin his interval after John picked a interval [start, end] are: start and also (i+1), for each lucky number i.
* Combining both strategies plus a quick way to count the total number of lucky numbers in an interval, we can have an O(L*L*log(L)) algorithm where L is the total number of lucky numbers in the range [a, b].
* As a subtask, use backtracking to generate all the relevant lucky numbers.
Code
The following Java implementation takes around 0.15 seconds in the worst case:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
public class TheLuckyGameDivOne {
long a, b;
long[] luckyNums;
int t;
// USe Backtrack to generate the lucky numbers.
void backtrack(long x) {
if (x <= b) {
if (a <= x) {
luckyNums[t++] = x;
}
backtrack(x * 10 + 4);
backtrack(x * 10 + 7);
}
}
int countLower(long x) {
//Counts lucky nums strictly less than x:
// Using binary search.
// Find minimum i: luckyNums[i]>=x
int lo = -1, hi = t;
while (lo + 1 < hi) {
int ha = (hi + lo) / 2;
if (luckyNums[ha] >= x) {
hi = ha;
} else {
lo = ha;
}
}
return hi;
}
// Counts the total amount of lucky numbers that are
// inside a Brus interval that begins at position x.
int F(long x, long bLen) {
return countLower(x + bLen) - countLower(x);
}
// Picks a interval for Brus such that it has
// the least lucky numbers.
int getBrus(long start, long end, long bLen) {
// try at start
int res = F(start, bLen);
//try positions right after every lucky number:
int hi = 0;
for (int j = 0; j < t; j++) {
if (luckyNums[j] + 1 >= start && luckyNums[j] + bLen <= end) {
res = Math.min(res, F(luckyNums[j] + 1, bLen));
}
}
return res;
}
public int find(long a, long b, long jLen, long bLen) {
//Prepare the backtracking.
luckyNums = new long[1 << 11];
this.a = a;
this.b = b;
t = 0;
backtrack(0);
// Sort so that we can use binary search
Arrays.sort(luckyNums, 0, t);
// Find the best result for John.
int bestJohn = 0;
//a may be a relevant position:
bestJohn = getBrus(a, a + jLen - 1, bLen);
// Try at every position (luckyNums[k] - bLen + 1) inside the range:
for (int k = 0; k < t; k++) {
long i = luckyNums[k] - bLen + 1;
if ((i > a) && (i + jLen - 1 <= b)) {
bestJohn = Math.max(bestJohn, getBrus(i, i + jLen - 1, bLen));
}
}
return bestJohn;
}
}